1. Field of the Invention
The present invention relates to layout verification for an integrated circuit device. More particularly, the present invention relates to a method for improving the process of design rule and layout versus schematic verification for integrated circuit devices.
2. Prior Art
In the design of an integrated circuit, a designer develops a high level language (e.g., VHDL) design and converts this into a netlist using circuit synthesis or logic capture computer implemented programs. The netlist represents logic elements and their interconnections that perform the desired circuit functions outlined in the high level circuit design. Using the netlist, a circuit layout is developed that translates the electrical symbols and connections into primitive geometric patterns ("primitives or geometry") from which transistors or other logic elements are formed and which are to be etched onto the semiconductor device.
The various primitives specify various geometric objects such as boxes, polygons, vias and wires. Cells are defined as either a geometric primitive, such as a single polygon, or as a combination of a plurality of primitives arranged to create a device, such as a transistor or a number of transistors. Since cells are respectively used in the design of an integrated device, it is convenient to identify each cell with a symbolic name that is easily manipulated on a computer. Each instance of this symbolic descriptor used in a circuit is then assembled into a sequence and format suitable for eventual output to a mask-making device or a direct-write-to-silicon semiconductor processing equipment. The sequential stream of symbolic descriptors are typically stored in a data storage device of a computer system and manipulated by computer-based processes to determine where each cell is to be placed on the integrated circuit and the interconnection between the cells. The sequential stream of symbolic descriptors is often called "layout data." One such format for storing and transferring this layout data is the GDSII format (graphic design stream). Layout data can be stored in hierarchical formats where parent cells can incorporate multiple child cells by referencing those cells.
It will be appreciated by one skilled in the art that as cells are assembled in a hierarchical manner by computer-based processes to build subsystems, and as subsystems are interconnected in a hierarchical manner to implement desired circuit functions, it is common for one or more layout design rules to be violated. Design rules specify permissible geometric patterns, minimum resolution, spacing between cells and other constraints of the integrated circuit manufacturing process that need be followed for proper operation of the devices and interconnections formed by the process. Although design rule violations may not necessarily result in a non-functional integrated circuit, production yields may be negatively impacted with a corresponding increase in the cost of manufacture or other circuit problems can result.
Design rule checking procedures (DRCs) and layout versus schematic (LVS) checking are executed on the layout data to determine if any violations exist on an integrated circuit layout design. It is desirable to arrive at a layout design that contains no design rule violations in before the design is committed to silicon or other semiconductor material. The LVS procedures compare the layout data to the actual logic elements of an integrated circuit design's netlist to determine if the layout data actually performs the proper logic functions as specified in the netlist. Violations occur where this mapping is faulty. It is desirable to arrive at a layout design that contains no LVS violations in before the design is committed to silicon or other semiconductor material.
Design rules may be checked either manually or by interpreting the symbolic stream with computer programs once the layout of an integrated circuit is available. In the past, DRC and LVS verification required the entire hierarchical representation, often referred to as the hierarchical tree, of the integrated circuit be processed entirely for each layout verification. The data can be processed using a flatten process or a hierarchical process. Under the flatten process, the design is completely flattened into the top level cell so as to remove all hierarchical structure. The flat representation is created by moving the geometry of leaf cells, e.g., those cells at the lowest level of the hierarchical tree, and the geometry of all intermediate cells, upward through the hierarchical structure until all layout data and interconnect information resides at the top level. The flat representation is then run through DRC and LVS checking. Each time an integrated circuit design is modified, it needs to be entirely flattened and entirely re-run through DRC and LVS checking procedures.
Using a hierarchical approach, the process is not entirely flattened but processed according to the hierarchical tree. However, even under this approach, each time an integrated circuit design is modified, it needs to be re-run through DRC and LVS checking procedures. However, performing DRC and LVS checking on a densely populated circuit (as performed by flat DRC programs) is memory and input/output (I/O) intensive and relatively inefficient in terms of computer processing time since each instance of a cell must be checked for conformity with the layout verification rules. In fact, layout verification programs can often take many hours to perform on high density integrated circuits. It would be advantageous to provide a layout verification system that can operate only on a portion of the design.
One problem with DRC and LVS checkers arises when the processes encounter juxtaposed cells. Overlap of adjacent cells can introduce layout errors not present in either cell prior to the overlap or can remove apparent errors that exist in the absence of the overlap. Early prior art methodologies prohibited overlap as a means to prevent unanticipated parasitic devices from being created by the overlap of cells. But merely prohibiting overlap of cells is not acceptable since circuit design requires that cells overlap to create, for example, full width conductors, inputs and outputs to the cell or to reduce the size of routing resources.
One improved hierarchical method for checking for design rules violations created by overlap areas is disclosed in Exploiting Structure in Integrated Circuit Design Analysis by Martin E, Newell and Daniel T. Fitzpatrick, 1982 Conference on Advanced Research in VLSI, M.I.T., Jan. 26, 1982, p. 84. The disclosed method employs a disjoint transformation to exploit the hierarchical nature of the typical integrated circuit design. The disjoint transformation removes overlapping cell instances by generating new cells from the overlapping area of these cells. The new cells are generated by recursively employing "split" and "gather" procedures. However, this method is inefficient since new must be cells created and design rule checks performed on each of the new cells. Further, the time to perform the disjoint transformation depends in large part on the degree of overlap present in the circuit and is not necessarily correlated with the number of transistors comprising the design.
Recognizing that greater efficiency could be achieved, later design rule checking methods check each cell in its environmental context by first identifying all elements that interact with the cell. On such method is disclosed in The Halo Algorithm--An Algorithm for Hierarchical Design of Rule Checking of VLSI Circuits, Nils Hedenstierna and Kjell O. Jeppson, IEEE Transaction On Computer-Aided Design of Integrated Circuits and Systems, Vol. 12, No. 2, February 1993. This reference discloses a hierarchical checking algorithm where each cell is checked in context of the environment in which the cell is used. One primarily purpose of this algorithm is to solve the problem of where to report a design rule violation (i.e., whether to include violations with the cell description as stored in the database structure or as part of all chip level instances of that cell).
This algorithm first generates a hierarchical tree to describe chip-level instances of cells hierarchically. The tree consists of all paths from the chip level instance to the most primitive cells, often referred to as instances of leaf cells. After generating the hierarchical tree, an inverse layout tree is derived for each leaf cell. The inverse layout tree is derived by treating the leaf cell as the root and taking all paths from the leaf cell to the chip-level. If the circuit design is regular, the inverse layout tree may be simplified to minimize memory requirements and will process faster. However, since multiple inverse trees must be derived, processing time and memory are increased. Further, it is not desirable to build and store inverse layout trees each time the circuit is modified. Inverse hierarchical trees do not represent the natural order in which hierarchical database information is stored in a layout file. Further still, it is not desirable to expend time or system resources in building large intermediate data structures.
Further, the above-described DRC and LVS checking processes are lengthy to perform and must be performed each time the design of the circuit is modified, even if the modification is relatively minor or isolated. Clearly, the prior art processes are inefficient particularly when DRC and LVS processes must be re-run on moderately or only slightly modified layout database information.
Accordingly, it is desirable to provide a method for verifying circuit layout of an integrated circuit, (e.g., performing design rule checks and/or LVS checks) while reducing demand on computer resources and time to complete the verification. The present invention offers the above by allowing layout verification only on a portion of the layout data. Further, it is desirable that the method provide an efficient means for detecting and checking overlapping geometric features to eliminate circuit errors. It is also desirable to perform efficient methods for flattening the layout data in those overlapping areas. The present invention provides the above advantages and other not specifically recited above but clear within the discussions of the present invention presented herein.